# /*
#  * @Author: TanFunWen 
#  * @Date: 2021-10-22 07:27:04 
#  * @Last Modified by:   TanFunWen 
#  * @Last Modified time: 2021-10-22 07:27:04 
#  */

# 找零兑换问题： 递归解法代码
import time

def recMc(coinValueList, change):
    minCoins = change
    if change in coinValueList:
        return 1
    else:
        for i in [ c for c in coinValueList if c <= change]:
            numCoins = 1 + recMc(coinValueList, change - i)
            if numCoins < minCoins:
                minCoins = numCoins
    return minCoins

def recDc(coinValueList, change, knownResults):
    minCoins = change
    if change in coinValueList:
        knownResults[change] = 1 # 记录最优解
        return 1
    elif knownResults[change] > 0:
        return knownResults[change]  # 查表成功，直接用最优解 
    else:
        for i in [c for c in coinValueList if c <= change]:
            numCoins = 1 + recDc(coinValueList, change -i ,knownResults)
            if numCoins < minCoins:
                minCoins = numCoins
                knownResults[change] = minCoins
    return minCoins

if __name__ == "__main__":
    start = time.time()
    print(recMc([1,5,10,25], 63))
    print('time used : {t} '.format(t=(time.time() - start)))

    start1 = time.time()
    print(recDc([1,5,10,25], 63, [0]*64))
    print('time used : {t} '.format(t=(time.time() - start1)))